SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Multifit algorithm</title>

</head>

Multifit algorithm

</h1>

</header>

The multifit algorithm is an algorithm for <a href="Multiway_number_partitioning" title="Multiway number partitioning">multiway number partitioning</a>, originally developed for the problem of <a href="Identical-machines_scheduling" title="Identical-machines scheduling">identical-machines scheduling</a>. It was developed by Coffman, Garey and Johnson.<a href="#cite_note-:0-1">[1]</a> Its novelty comes from the fact that it uses an algorithm for another famous problem - the <a href="Bin_packing_problem" title="Bin packing problem">bin packing problem</a> - as a subroutine.

<div class="mw-heading mw-heading2"><h2 id="The_algorithm">The algorithm</h2></div>

The input to the algorithm is a set S of numbers, and a parameter n. The required output is a partition of S into n subsets, such that the largest subset sum (also called the makespan) is as small as possible.

The algorithm uses as a subroutine, an algorithm called <a href="First-fit-decreasing_bin_packing" title="First-fit-decreasing bin packing">first-fit-decreasing bin packing</a> (FFD). The FFD algorithm takes as input the same set S of numbers, and a bin-capacity c. It heuristically packs numbers into bins such that the sum of numbers in each bin is at most C, aiming to use as few bins as possible. Multifit runs FFD multiple times, each time with a different capacity C, until it finds some C such that FFD with capacity C packs S into at most n bins. To find it, it uses <a href="Binary_search" title="Binary search">binary search</a> as follows.

<ol><li>Let L := max ( sum(S) / n, max(S) ). Note, with bin-capacity smaller than L, every packing must use more than n bins.</li>

<li>Let U := max ( 2 sum(S) / n, max(S) ). Note, with bin-capacity at least U, FFD uses at most n bins. Proof: suppose by contradiction that some input si did not fit into any of the first n bins. Clearly this is possible only if i ≥ n+1. If si > C/2, then, since the inputs are ordered in descending order, the same inequality holds for all the first n+1 inputs in S. This means that sum(S) > (n+1)C/2 > n U/2, a contradiction to the definition of U. Otherwise, si ≤ C/2. So the sum of each of the first n bins is more than C/2. This again implies sum(S) > n C/2 > n U/2, contradiction.</li>

<li>Iterate k times (where k is a precision parameter):

<ul><li>Let C := (L+U)/2. Run FFD on S with capacity C.

<ul><li>If FFD needs at most n bins, then decrease U by letting U := C.</li>

<li>If FFD needs more than n bins, then increase L by letting L := C.</li></ul></li></ul></li>

<li>Finally, run FFD with capacity U. It is guaranteed to use at most n bins. Return the resulting scheduling.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Performance">Performance</h2></div>

Multifit is a <a href="Constant_factor_approximation_algorithm" class="mw-redirect" title="Constant factor approximation algorithm">constant-factor approximation algorithm</a>. It always finds a partition in which the makespan is at most a constant factor larger than the optimal makespan. To find this constant, we must first analyze FFD. While the standard analysis of <a href="First-fit-decreasing_bin_packing" title="First-fit-decreasing bin packing">FFD</a> considers approximation w.r.t. number of bins when the capacity is constant, here we need to analyze approximation w.r.t. capacity when the number of bins is constant. Formally, for every input size S and integer n, let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle OPT(S,n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(S,n)}</annotation>

</semantics>

</math><img src="./c023058e8c95d3b68b3dffc4ec65293a44917e70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.892ex; height:2.843ex;" alt="{\displaystyle OPT(S,n)}" loading="lazy"> be the smallest capacity such that S can be packed into n bins of this capacity. Note that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle OPT(S,n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(S,n)}</annotation>

</semantics>

</math><img src="./c023058e8c95d3b68b3dffc4ec65293a44917e70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.892ex; height:2.843ex;" alt="{\displaystyle OPT(S,n)}" loading="lazy"> is the value of the optimal solution to the original scheduling instance.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}}</annotation>

</semantics>

</math><img src="./57784cdf7f49f2c46baad4eb7b6a7d5c14eb5fa4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.267ex; height:2.009ex;" alt="{\displaystyle r_{n}}" loading="lazy"> be the smallest real number such that, for every input S, FFD with capacity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}\cdot OPT(S,n)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\cdot OPT(S,n)}</annotation>

</semantics>

</math><img src="./adcce81a5815e5f5f72b61ad1f7fe5ac69ee542b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.838ex; height:2.843ex;" alt="{\displaystyle r_{n}\cdot OPT(S,n)}" loading="lazy"> uses at most n bins.

<div class="mw-heading mw-heading3"><h3 id="Upper_bounds">Upper bounds</h3></div>

Coffman, Garey and Johnson prove the following upper bounds on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}}</annotation>

</semantics>

</math><img src="./57784cdf7f49f2c46baad4eb7b6a7d5c14eb5fa4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.267ex; height:2.009ex;" alt="{\displaystyle r_{n}}" loading="lazy">:<a href="#cite_note-:0-1">[1]</a>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\leq 8/7\approx 1.14}</annotation>

</semantics>

</math><img src="./387485f41cfb4425393a7fdcc40292d2a46debca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.086ex; height:2.843ex;" alt="{\displaystyle r_{n}\leq 8/7\approx 1.14}" loading="lazy"> for n = 2;</li>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\leq 15/13\approx 1.15}</annotation>

</semantics>

</math><img src="./5f471b8b06b08ec77fe92645351bc793e0648d5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.411ex; height:2.843ex;" alt="{\displaystyle r_{n}\leq 15/13\approx 1.15}" loading="lazy"> for n = 3;</li>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\leq 20/17\approx 1.176}</annotation>

</semantics>

</math><img src="./1288f0420aa4dfd9abd63ca3c85aa540d437449d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.573ex; height:2.843ex;" alt="{\displaystyle r_{n}\leq 20/17\approx 1.176}" loading="lazy"> for n = 4,5,6,7;</li>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\leq 122/100=1.22}</annotation>

</semantics>

</math><img src="./bae6178abcb9d76709f734be58cb0131d633c817.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.735ex; height:2.843ex;" alt="{\displaystyle r_{n}\leq 122/100=1.22}" loading="lazy"> for all n ≥ 8.</li></ul>

During the MultiFit algorithm, the lower bound L is always a capacity for which it is impossible to pack S into n bins. Therefore, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L<r_{n}\cdot OPT(S,n)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L<r_{n}\cdot OPT(S,n)}</annotation>

</semantics>

</math><img src="./b8ad9047c9308406f3614c2aff638f691b8cdb3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.52ex; height:2.843ex;" alt="{\displaystyle L<r_{n}\cdot OPT(S,n)}" loading="lazy">. Initially, the difference <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U-L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U-L}</annotation>

</semantics>

</math><img src="./998f89a79b7c2fc4cd1e14133e68cb7226b1502f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.206ex; height:2.343ex;" alt="{\displaystyle U-L}" loading="lazy"> is at most sum(S) / n, which is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle OPT(S,n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(S,n)}</annotation>

</semantics>

</math><img src="./c023058e8c95d3b68b3dffc4ec65293a44917e70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.892ex; height:2.843ex;" alt="{\displaystyle OPT(S,n)}" loading="lazy">. After the MultiFit algorithm runs for k iterations, the difference shrinks k times by half, so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U-L\leq (1/2)^{k}\cdot OPT(S,n)}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U-L\leq (1/2)^{k}\cdot OPT(S,n)}</annotation>

</semantics>

</math><img src="./3b185e5213b4c4b8015115733948d5b9addd100d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.261ex; height:3.176ex;" alt="{\displaystyle U-L\leq (1/2)^{k}\cdot OPT(S,n)}" loading="lazy">. Therefore, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)}">

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)}</annotation>

</semantics>

</math><img src="./f97eab3e90c68a7569a6369ea6cd1571db10f6a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.755ex; height:3.176ex;" alt="{\displaystyle U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)}" loading="lazy">. Therefore, the scheduling returned by MultiFit has makespan at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}+(1/2)^{k}}">

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}+(1/2)^{k}}</annotation>

</semantics>

</math><img src="./9a3caed90a823c23bec8a93fded8c5cc4d7ca959.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.493ex; height:3.176ex;" alt="{\displaystyle r_{n}+(1/2)^{k}}" loading="lazy"> times the optimal makespan. When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is sufficiently large, the approximation factor of MultiFit can be made arbitrarily close to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}}</annotation>

</semantics>

</math><img src="./57784cdf7f49f2c46baad4eb7b6a7d5c14eb5fa4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.267ex; height:2.009ex;" alt="{\displaystyle r_{n}}" loading="lazy">, which is at most 1.22.

Later papers performed a more detailed analysis of MultiFit, and proved that its approximation ratio is at most 6/5=1.2,<a href="#cite_note-:1-2">[2]</a> and later, at most 13/11≈1.182.<a href="#cite_note-:2-3">[3]</a> The original proof of this missed some cases; <a href="#cite_note-4">[4]</a> presented a complete and simpler proof. The 13/11 cannot be improved: see lower bound below.<a href="#cite_note-:1-2">[2]</a>

<div class="mw-heading mw-heading3"><h3 id="Lower_bounds">Lower bounds</h3></div>

For n=4: the following<a href="#cite_note-:3-5">[5]</a> shows that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}\geq 20/17}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\geq 20/17}</annotation>

</semantics>

</math><img src="./b7bdfe17c5d1d2a7403a8896e469d327b0e185be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.178ex; height:2.843ex;" alt="{\displaystyle r_{n}\geq 20/17}" loading="lazy">, which is tight. The inputs are 9,7,6,5,5, 4,4,4,4,4,4,4,4,4. They can be packed into 4 bins of capacity 17 as follows:

But if we run FFD with bin capacity smaller than 20, then the filled bins are:

Note that the sum in each of the first 4 bins is 16, so we cannot put another 4 inside it. Therefore, 4 bins are not sufficient.

For n=13: the following<a href="#cite_note-:1-2">[2]</a> shows that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}\geq 13/11}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\geq 13/11}</annotation>

</semantics>

</math><img src="./62ca9c519e8eee5b201c0048c0636f144e3f6264.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.178ex; height:2.843ex;" alt="{\displaystyle r_{n}\geq 13/11}" loading="lazy">, which is tight. The inputs can be packed into 13 bins of capacity 66 as follows:

<ul><li>40,13,13 {8 times}</li>

<li>25,25,16 {3 times}</li>

<li>25,24,17 {2 times}</li></ul>

But if we run FFD with bin capacity smaller than 66*13/11 = 78, then the filled bins are:

<ul><li>40,25 {8 times}</li>

<li>13, 13, 13, 13, 13 {3 times}</li>

Note that the sum in each of the first 13 bins is 65, so we cannot put another 13 inside it. Therefore, 13 bins are not sufficient.

<div class="mw-heading mw-heading3"><h3 id="Performance_with_uniform_machines">Performance with uniform machines</h3></div>

MultiFit can also be used in the more general setting called <a href="Uniform-machines_scheduling" title="Uniform-machines scheduling">uniform-machines scheduling</a>, where machines may have different processing speeds.<a href="#cite_note-6">[6]</a> When there are two uniform machines, the approximation factor is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {6}}/2}">

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {6}}/2}</annotation>

</semantics>

</math><img src="./2c1656d1466734d59460fa63d718ab738c83b933.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.423ex; height:3.009ex;" alt="{\displaystyle {\sqrt {6}}/2}" loading="lazy">. When MultiFit is combined with the <a href="LPT_algorithm" class="mw-redirect" title="LPT algorithm">LPT algorithm</a>, the ratio improves to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {2}}+1/2}">

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {2}}+1/2}</annotation>

</semantics>

</math><img src="./599d59288ea26f41ed76b0c1981b1b47e06d269a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.426ex; height:3.176ex;" alt="{\displaystyle {\sqrt {2}}+1/2}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Performance_for_maximizing_the_smallest_sum">Performance for maximizing the smallest sum</h3></div>

A dual goal to minimizing the largest sum (makespan) is maximizing the smallest sum. Deuermeyer, Friesen and Langston claim that MultiFit does not have a good approximation factor for this problem:<a href="#cite_note-:4-7">[7]</a><blockquote>"In the solution of the makespan problem using MULTIFIT, it is easy to construct examples where one processor is never used. Such a solution is tolerable for the makespan problem, but is totally unacceptable for our problem [since the smallest sum is 0]. Modifications of MULTIFIT can be devised which would be more suitable for our problem, but we could find none which produces a better worst-case bound than that of <a href="Longest-processing-time-first_scheduling" title="Longest-processing-time-first scheduling">LPT</a>."</blockquote>

<div class="mw-heading mw-heading2"><h2 id="Proof_idea">Proof idea</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Minimal_counterexamples">Minimal counterexamples</h3></div>

The upper bounds on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}}</annotation>

</semantics>

</math><img src="./57784cdf7f49f2c46baad4eb7b6a7d5c14eb5fa4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.267ex; height:2.009ex;" alt="{\displaystyle r_{n}}" loading="lazy"> are proved by contradiction. For any integers p ≥ q, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}>p/q}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}>p/q}</annotation>

</semantics>

</math><img src="./8ac515f02b778a5cc08b35b0075e9ed346cc6901.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.767ex; height:2.843ex;" alt="{\displaystyle r_{n}>p/q}" loading="lazy">, then there exists a (p/q)-counterexample, defined as an instance S and a number n of bins such that

<ul><li>S can be packed into n bins with capacity q;</li>

<li>FFD does not manage to pack S into n bins with capacity p.</li></ul>

If there exists such a counterexample, then there also exists a minimal (p/q)-counterexample, which is a (p/q)-counterexample with a smallest number of items in S and a smallest number of bins n. In a minimal (p/q)-counterexample, FFD packs all items in S except the last (smallest) one into n bins with capacity p. Given a minimal (p/q)-counterexample, denote by P1,...,Pn the (incomplete) FFD packing into these n bins with capacity p, by Pn+1 the bin containing the single smallest item, and by Q1,...,Qn the (complete) optimal packing into n bins with capacity q. The following lemmas can be proved:

<ul><li>No union of k subsets from {Q1,...,Qn} is dominated by a union of k subsets from {P1,...,Pn+1} ("dominated" means that each item in the dominated subset is mapped to a weakly-larger item in the dominating subset). Otherwise we could get a smaller counterexample as follows. [1] Delete all items in the Pi. Clearly, the incomplete FFD packing now needs n-k bins, and still the smallest item (or an entire bin) remains unpacked. [2] In the optimal packing Qi, exchange each item with its dominating item. Now, the k subsets Qi are larger (probably larger than q), but all other n-k subsets are smaller (in particular, at most q). Therefore, after deleting all items in the Pi, the remaining items can be packed into at most n-k bins of size q.</li>

<li>Each of Q1,...,Qn contains at least 3 items. Otherwise we had domination and, by the previous lemma, could get a smaller counterexample. This is because [a] each Qi with a single item is dominated by the Pj that contains that item; [b] for each Qi with two items x and y, if both x and y are in the same Pj, then Qi is dominated by this Pj; [c] Suppose x≥y, x is in some Pj, and y is in some Pk to its right. This means that y did not fit into Pj. But x+y ≤ q. This means that Pj must contain some item z ≥ y. So Qi is dominated by Pj. [d] Suppose x≥y, x is in some Pj, and y is in some Pk to its left. This means that there must be a previous item z ≥ x. So Qi is dominated by Pk.</li>

<li>Each of P1,...,Pn contains at least 2 items. This is because, if some Pi contains only a single item, this implies that the last (smallest) item does not fit into it. This means that this single item must be alone in an optimal bundle, contradicting the previous lemma.</li>

<li>Let s be the size of the smallest item. Then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s>{\frac {n}{n-1}}(p-q)}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s>{\frac {n}{n-1}}(p-q)}</annotation>

</semantics>

</math><img src="./032bd413ccd0a5f1a69b5debd62102cc37778c80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:17.311ex; height:4.843ex;" alt="{\displaystyle s>{\frac {n}{n-1}}(p-q)}" loading="lazy">. Proof: Since s does not fit into the first n bundles, we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle sum(P_{i})+s>p}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle sum(P_{i})+s>p}</annotation>

</semantics>

</math><img src="./2686df8f635d070a2712f4c5ea1734b30134dcca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.761ex; height:2.843ex;" alt="{\displaystyle sum(P_{i})+s>p}" loading="lazy">, so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i=1}^{n}sum(P_{i})+n\cdot s>n\cdot p}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}sum(P_{i})+n\cdot s>n\cdot p}</annotation>

</semantics>

</math><img src="./643d5e118b5f4ab36c9a28c2479047f6c6ef5891.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:26.65ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{n}sum(P_{i})+n\cdot s>n\cdot p}" loading="lazy">. On the other hand, since all items fit into n bins of capacity q, we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q}</annotation>

</semantics>

</math><img src="./2ceb988ed45ea0dd192dc4fcb12cce60947d8f45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:23.477ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q}" loading="lazy">. Subtracting the inequalities gives <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s>{\frac {n}{n-1}}(p-q)}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s>{\frac {n}{n-1}}(p-q)}</annotation>

</semantics>

</math><img src="./032bd413ccd0a5f1a69b5debd62102cc37778c80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:17.311ex; height:4.843ex;" alt="{\displaystyle s>{\frac {n}{n-1}}(p-q)}" loading="lazy">.</li>

<li>The size of every item is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q-2s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q-2s}</annotation>

</semantics>

</math><img src="./33bdb706876351a045ca54376ee75a343dfa13de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.163ex; height:2.509ex;" alt="{\displaystyle q-2s}" loading="lazy">. This is because there are at least 3 items in each optimal bin (with capacity q).</li>

<li>The sum of items in every bin P1,...,Pn is larger than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p-s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p-s}</annotation>

</semantics>

</math><img src="./a83132e7db5dade59a46caad2eb21ca2a0eba088.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.19ex; height:2.343ex;" alt="{\displaystyle p-s}" loading="lazy">; otherwise we could add the smallest item.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="5/4_Upper_bound">5/4 Upper bound</h3></div>

From the above lemmas, it is already possible to prove a loose upper bound <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}\leq 5/4=1.25}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\leq 5/4=1.25}</annotation>

</semantics>

</math><img src="./c76a7adae592451ffaa5c406bd65baac19d4a54e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.086ex; height:2.843ex;" alt="{\displaystyle r_{n}\leq 5/4=1.25}" loading="lazy">. Proof. Let S, n be a minimal (5/4)-counterexample. The above lemmas imply that -

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s>{\frac {n}{n-1}}(5-4)>1}</annotation>

</semantics>

</math><img src="./4df35a825c76900b0cd34d95afec890833b2ce62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:21.658ex; height:4.843ex;" alt="{\displaystyle s>{\frac {n}{n-1}}(5-4)>1}" loading="lazy">. Since the optimal capacity is 4, no optimal bin can contain 4 or more items. Therefore, each optimal bin must contain at most 3 items, and the number of items is at most 3n.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4-2s}</annotation>

</semantics>

</math><img src="./31ed2be1974c8b76aa901c43871c2be3a8ad9c60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.256ex; height:2.343ex;" alt="{\displaystyle 4-2s}" loading="lazy">, and the size of each FFD bin is more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 5-s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 5-s}</annotation>

</semantics>

</math><img src="./7bd2f78b9266987320e6c4db49fe9526886c855a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.093ex; height:2.343ex;" alt="{\displaystyle 5-s}" loading="lazy">. If some FFD bin contained only two items, its sum would be at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 8-4s=5+(3-3s)-s<5-s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 8-4s=5+(3-3s)-s<5-s}</annotation>

</semantics>

</math><img src="./721a86154b661c9cc4e3c618e189182a241531cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.545ex; height:2.843ex;" alt="{\displaystyle 8-4s=5+(3-3s)-s<5-s}" loading="lazy">; so each FFD bin must contain at least 3 items. But this means that FFD yields exactly n bins - a contradiction.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Structure_of_FFD_packing">Structure of FFD packing</h3></div>

To prove tighter bounds, one needs to take a closer look at the FFD packing of the minimal (p/q)-counterexample. The items and FFD bins P1,...,Pn are termed as follows:

<ul><li>A regular item is an item added to some bin Pi, before the next bin Pi+1 was opened. Equivalently, a regular item is an item in Pi which is at least as large as every item in every bin Pj for j>i.</li>

<li>A fallback item is an item added to some bin Pi, after the next bin Pi+1 was opened. Equivalently, a fallback item is an item in Pi which is smaller than the largest item in Pi+1.</li>

<li>A regular k-bin is a bin that contains k regular items and no fallback items.</li>

<li>A fallback k-bin is a bin that contains k regular items and some fallback items.</li></ul>

The following lemmas follow immediately from these definitions and the operation of FFD.

<li>If Pi is a k-bin, then the sum of the k regular items in Pi is larger than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {k}{k+1}}\cdot p}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {k}{k+1}}\cdot p}</annotation>

</semantics>

</math><img src="./753605c5b66fa38a09e9baa9d0511b35e3941caa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:8.899ex; height:5.676ex;" alt="{\displaystyle {\frac {k}{k+1}}\cdot p}" loading="lazy">, since otherwise we could add another item before opening a new bin.</li>

<li>If Pi and Pi+1 are both k-bins, and then the sum of the k regular items in Pi is at least as large as in Pi+1 (this is because the items are ordered by decreasing size).</li>

<li>All regular k-bins are to the left of all fallback k-bins. This is because all bins have the same capacity, so if more fallback items fit into a bin, these items must be smaller, so they must be allocated later.</li></ul>

In a minimal counterexample, there are no regular 1-bins (since each bin contains at least 2 items), so by the above lemmas, the FFD bins P1,...,Pn are ordered by type:

<ul><li>Zero or more fallback 1-bins;</li>

<li>Then, zero or more regular 2-bins;</li>

<li>Then, zero or more fallback 2-bins;</li>

<li>Then, zero or more regular 3-bins;</li>

<li>Then, zero or more fallback 3-bins;</li>

<div class="mw-heading mw-heading3"><h3 id="1.22_upper_bound">1.22 upper bound</h3></div>

The upper bound <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}\leq 1.22}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\leq 1.22}</annotation>

</semantics>

</math><img src="./3892ce0464177882f588e73768da576340ce12b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.5ex; height:2.509ex;" alt="{\displaystyle r_{n}\leq 1.22}" loading="lazy"><a href="#cite_note-:0-1">[1]</a> is proved by assuming a minimal (122/100)-counterexample. Each item is given a weight based on its size and its bin in the FFD packing. The weights are determined such that the total weight in each FFD bin is at least x, and the total weight in almost each optimal bin is at most x (for some predetermined x). This implies that the number of FFD bins is at most the number of optimal bins, which contradicts the assumption that it is a counterexample.

By the lemmas above, we know that:

<ul><li>The size of the smallest item satisfies s > p-q = 22, so s = 22+D for some D>0.</li>

<li>Each optimal bin contains at most 4 items (floor(100/22)), and each FFD bin contains at most 5 items (floor(122/22)).</li>

<li>The size of every item is at most q-2s = 56-2D.</li>

<li>The sum in each FFD bin is larger than p-s = 100-D.</li>

<li>There are no 1-bins, since in a 1-bin, the size of the regular item must be at least p/2=61, while here the size of every item is less than 56.</li></ul>

If D>4, the size of each item is larger than 26, so each optimal bin (with capacity 100) must contain at most 3 items. Each item is smaller than 56-2D and each FFD bin has a sum larger than 100-D, so each FFD bin must contain at least 3 items. Therefore, there are at most n FFD bins - contradiction. So from now on, we assume D≤4. The items are assigned types and weights as follows.

<ul><li>The two items in each regular 2-bin except maybe the last one have a size larger than (100-D)/2 each. All such items are called type-X2, and assigned a weight of (100-D)/2. The last 2-regular bin is a special case: if both its items have a size larger than (100-D)/2, then they are type-X2 too; otherwise, they are called type-Z, and their weight equals their size.</li>

<li>The two regular items in each fallback 2-bin have a total size larger than 2*122/3; they are called type-Y2, and their weight equals their size minus D.</li>

<li>The three items in each regular 3-bin except maybe the last one have a size larger than (100-D)/3 each. All such items are called type-X3, and assigned a weight of (100-D)/3. The last 3-regular bin is a special case: if all items in it have a size larger than (100-D)/3, then they are type-X3 too; otherwise, they are called type-Z and their weight equals their size.</li>

<li>The three regular items in each fallback 3-bin have a total size larger than 3*122/4; they are called type-Y3, and their weight equals their size minus D.</li>

<li>The four items in each regular 4-bin except maybe the last one have a size larger than (100-D)/4 each. All such items are called type-X4, and assigned a weight of (100-D)/4. The last 4-regular bin is a special case: if all items in it have a size larger than (100-D)/4, then they are type-X4 too; otherwise, they are called type-Z and their weight equals their size.</li>

<li>The remaining items (including all fallback items in fallback 2-bins and 3-bins, all fallback 4-bins, and all other 5-item bins) are all called type-X5, and their weight equals 22 (if D ≤ 12/5) or (100-D)/4 (otherwise). The threshold 12/5 was computed such that the weight is always at most 22+D, so that the weight is always smaller than the size.</li></ul>

Note that the weight of each item is at most its size (the weight can be seen as the size "rounded down"). Still, the total weight of items in every FFD bin is at least 100-D:

<ul><li>For regular 2-bins, regular 3-bins and regular 4-bins:

<ul><li>For the non-last ones, this is immediate.</li>

<li>The last such bins contain only Z-type items, whose weight equals their size, so the total weight of these bins equals their total size, which is more than 100-D.</li></ul></li>

<li>Fallback 2-bins contain two type-Y2 items with total weight larger than 2*122/3-2D, plus at least one type-X5 item with weight at least 22 (if D ≤ 12/5) or (100-D)/4 (otherwise). In both cases the total weight is more than 100-D.</li>

<li>Fallback 3-bins contain three type-Y3 items with total weight larger than 3*122/4-3D, plus at least one type-X5 item with weight at least 22. So the total weight is more than 3*122/4+22-3D = 113.5-3D ≥ 105.5-D > 100-D, since D≤4.</li>

<li>5-item bins contain 5 items with size at least 22+D and weight at least 22, so their total weight is obviously more than 100-D.</li></ul>

The total weight of items in most optimal bins is at most 100-D:

<ul><li>This is clear for any optimal bin containing a type-Y2 item or a type-Y3 item, since their weight is their size minus D, the weights of other items is at most their size, and the total size of an optimal bin is at most 100.</li>

<li>For optimal bins containing only type-X2, type-X3, type-X4 and type-X5 items, it is possible to check all possible configurations (all combinations that fit into an optimal bin of size 100), and verify that the total weight in each configuration is at most 100-D.</li>

<li>Optimal bins containing type-Z items might have a total weight larger than 100-D. Since the total weight is at most 100, there is an "excess weight" of at most D for each such bin. However, the number of type-Z items is limited:

<ul><li>If D > 12/5, then there are at most 5 type-Z items (2 in the last regular 2-bin and 3 in the last regular 3-bin; the items in the last regular 4-bin are all type-X4). Therefore, the excess weight is at most 5D. Comparing the total weight of FFD vs. optimal bins yields s < 5D ≤ 20 < 22, a contradiction.</li>

<li>Otherwise, there are at most 9 type-Z items (2+3+4). Therefore, the excess weight is at most 9D. Comparing the total weight of FFD vs. optimal bins yields s < 9D ≤ 108/5 < 22, a contradiction.</li></ul></li></ul>

<div class="mw-heading mw-heading3"><h3 id="13/11_upper_bound">13/11 upper bound</h3></div>

The upper bound <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}\leq 13/11\approx 1.182}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}\leq 13/11\approx 1.182}</annotation>

</semantics>

</math><img src="./1b571af461a6a84f0783bdf5273987fe7f7f2066.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.573ex; height:2.843ex;" alt="{\displaystyle r_{n}\leq 13/11\approx 1.182}" loading="lazy"><a href="#cite_note-:2-3">[3]</a> is proved by assuming a minimal ((120-3d)/100)-counterexample, with some d<20/33, and deriving a contradiction.

<div class="mw-heading mw-heading2"><h2 id="Non-monotonicity">Non-monotonicity</h2></div>

MultiFit is not monotone in the following sense: it is possible that an input decreases while the max-sum in the partition returned by MultiFit increases. As an example,<a href="#cite_note-:0-1">[1]</a>: Fig.4 suppose n=3 and the input numbers are:<blockquote>44, 24, 24, 22, 21, 17, 8, 8, 6, 6.</blockquote>FFD packs these inputs into 3 bins of capacity 60 (which is optimal):

But if the "17" becomes "16", then FFD with capacity 60 needs 4 bins:

so MultiFit must increase the capacity, for example, to 62:

This is in contrast to other number partitioning algorithms - <a href="List_scheduling" title="List scheduling">List scheduling</a> and <a href="Longest-processing-time-first_scheduling" title="Longest-processing-time-first scheduling">Longest-processing-time-first scheduling</a> - which are monotone.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Generalization:_fair_allocation_of_chores">Generalization: fair allocation of chores</h2></div>

Multifit has been extended to the more general problem of <a href="Maximin-share" class="mw-redirect" title="Maximin-share">maximin-share</a> allocation of chores.<a href="#cite_note-:3-5">[5]</a> In this problem, S is a set of chores, and there are n agents who assign potentially different valuations to the chores. The goal is to give to each agent, a set of chores worth at most r times the maximum value in an optimal scheduling based on i's valuations. A naive approach is to let each agent in turn use the MultiFit algorithm to calculate the threshold, and then use the algorithm where each agent uses his own threshold. If this approach worked, we would get an approximation of 13/11. However, this approach fails due to the <a href="First-fit-decreasing_bin_packing#monotonicity" title="First-fit-decreasing bin packing">non-monotonicity of FFD</a>.

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

Here is an example.<a href="#cite_note-:3-5">[5]</a>: Ex.5.2 Suppose there are four agents, and they have valuations of two types:

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th>

<th>

</th></tr>

<tr>

<td>Type A:

</td>

<td>51

</td>

<td>27.5

</td>

<td>27.5

</td>

<td>27.5

</td>

<td>27.5

</td>

<td>25

</td>

<td>12

</td>

<td>12

</td>

<td>10

</td>

<td>10

</td>

<td>10

</td>

<td>10

</td>

<td>10

</td>

<td>10

</td>

<td>10

</td>

<td>10

</td>

<td>10

</td></tr>

<tr>

<td>Type B:

</td>

<td>51

</td>

<td>27.5

</td>

<td>27.5

</td>

<td>27.5

</td>

<td>27.5

</td>

<td>24

</td>

<td>20

</td>

<td>20

</td>

<td>8.33

</td>

<td>8.33

</td>

<td>8.33

</td>

<td>8.33

</td>

<td>8.33

</td>

<td>8.33

</td>

<td>8.33

</td>

<td>8.33

</td>

<td>8.33

</td></tr></tbody></table>

Both types can partition the chores into 4 parts of total value 75. Type A:

Type B:

<li>8.33 {9 times}</li></ul>

If all four agents are of the same, then FFD with threshold 75 fills the 4 optimal bins. But suppose there is one agent of type B, and the others are of type A. Then, in the first round, the agent of type B takes the bundle 51, 24 (the other agents cannot take it since for them the values are 51,25 whose sum is more than 75).In the following rounds, the following bundles are filled for the type A agents:

<ul><li>27.5, 27.5, 12 [the sum is 67 - there is no room for another 10]</li>

<li>27.5, 27.5, 12 [the sum is 67 - there is no room for another 10]</li>

<li>10, 10, 10, 10, 10, 10, 10 [the sum is 70 - there is no room for another 10]</li></ul>

so the last two chores remain unallocated.

<div class="mw-heading mw-heading3"><h3 id="Optimal_value_guarantee">Optimal value guarantee</h3></div>

Using a more sophisticated threshold calculation, it is possible to guarantee to each agent at most 11/9≈1.22 of his optimal value if the optimal value is known, and at most 5/4≈1.25 of his optimal value (using a polynomial time algorithm) if the optimal value is not known.<a href="#cite_note-:3-5">[5]</a>

Using more elaborate arguments, it is possible to guarantee to each agent the same ratio of MultiFit.<a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2></div>

<ul><li>Python: The <a rel="nofollow" class="external text" href="https://github.com/erelsgl/prtpy">prtpy package</a> contains <a rel="nofollow" class="external text" href="https://github.com/erelsgl/prtpy/blob/main/prtpy/partitioning/multifit.py">an implementation of multifit</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCoffmanGareyJohnson1978" class="citation journal cs1">Coffman, Jr., E. G.; Garey, M. R.; Johnson, D. S. (1978-02-01). <a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/abs/10.1137/0207001">"An Application of Bin-Packing to Multiprocessor Scheduling"</a>. SIAM Journal on Computing. 7 (1): 1–17. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0207001">10.1137/0207001</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-:1-2">^ <a href="#cite_ref-:1_2-0">a</a> <a href="#cite_ref-:1_2-1">b</a> <a href="#cite_ref-:1_2-2">c</a> <cite id="CITEREFFriesen1984" class="citation journal cs1">Friesen, Donald K. (1984-02-01). <a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/abs/10.1137/0213013">"Tighter Bounds for the Multifit Processor Scheduling Algorithm"</a>. SIAM Journal on Computing. 13 (1): 170–181. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0213013">10.1137/0213013</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>.</cite>

</li>

<li id="cite_note-:2-3">^ <a href="#cite_ref-:2_3-0">a</a> <a href="#cite_ref-:2_3-1">b</a> <cite id="CITEREFYue1990" class="citation journal cs1">Yue, Minyi (1990-12-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF02216826">"On the exact upper bound for the multifit processor scheduling algorithm"</a>. Annals of Operations Research. 24 (1): 233–259. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02216826">10.1007/BF02216826</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1572-9338">1572-9338</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:120965788">120965788</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFCao1995" class="citation cs2">Cao, Feng (1995), Du, Ding-Zhu; Pardalos, Panos M. (eds.), <a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-1-4613-3557-3_5">"Determining the Performance Ratio of Algorithm Multifit for Scheduling"</a>, Minimax and Applications, Nonconvex Optimization and Its Applications, vol. 4, Boston, MA: Springer US, pp. 79–96, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4613-3557-3_5">10.1007/978-1-4613-3557-3_5</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4613-3557-3</bdi>, retrieved 2021-08-23</cite>

</li>

<li id="cite_note-:3-5">^ <a href="#cite_ref-:3_5-0">a</a> <a href="#cite_ref-:3_5-1">b</a> <a href="#cite_ref-:3_5-2">c</a> <a href="#cite_ref-:3_5-3">d</a> <cite id="CITEREFHuangLu2021" class="citation book cs1">Huang, Xin; Lu, Pinyan (2021-07-18). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3465456.3467555">"An Algorithmic Framework for Approximating Maximin Share Allocation of Chores"</a>. Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. New York, NY, USA: Association for Computing Machinery. pp. 630–631. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1907.04505">1907.04505</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3465456.3467555">10.1145/3465456.3467555</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-8554-1</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:195874333">195874333</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFBurkardHe1998" class="citation journal cs1">Burkard, R. E.; He, Y. (1998-09-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF02684354">"A note on MULTIFIT scheduling for uniform machines"</a>. Computing. 61 (3): 277–283. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02684354">10.1007/BF02684354</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1436-5057">1436-5057</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:37590584">37590584</a>.</cite>

</li>

<li id="cite_note-:4-7"><a href="#cite_ref-:4_7-0">^</a> <cite id="CITEREFDeuermeyerFriesenLangston1982" class="citation journal cs1">Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (June 1982). "Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System". SIAM Journal on Algebraic and Discrete Methods. 3 (2): 190–196. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0603019">10.1137/0603019</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFSegal-Halevi2021" class="citation cs2">Segal-Halevi, Erel (2021-10-17), On Monotonicity of Number-Partitioning Algorithms, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2110.08886">2110.08886</a></cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFHuangSegal-Halevi2023" class="citation cs2">Huang, Xin; Segal-Halevi, Erel (2023-12-13), A Reduction from Chores Allocation to Job Scheduling, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2302.04581">2302.04581</a></cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-23" href="https://en.wikipedia.org/wiki/?title=Multifit_algorithm&oldid=1291825897">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>